Ma trận kề của một đồ thị vô hướng có tính đối xứng, và do đó có một tập đầy đủ các giá trị riêng (eigenvalue) và cơ sở vector riêng (eigenvector) trực giao. Tập các giá trị riêng của đồ thị là phổ của đồ thị.

Giả sử cho trước hai đồ thị có hướng hoặc vô hướng G1 và G2 với các ma trận kề A1 và A2. G1 và G2 đẳng cấu (isomorphic) khi và chỉ khi tồn tại một ma trận hoán vị (permutation matrix) P sao cho

Cụ thể là A1 và A2 là các ma trận đồng dạng và do đó có cùng đa thức cực tiểu (minimal polynomial), đa thức đặc trưng (characteristic polynomial), các giá trị riêng, định thức (determinant) và vết của ma trận (trace). Do đó chúng có thể được dùng như các bất biến đẳng cấu của đồ thị. Cho trước hai ma trận kề, có thể xây dựng lại ma trận hoán vị đã được sử dụng: xem chi tiết tại Ma trận hoán vị.

Tuy nhiên, cần lưu ý rằng điều ngược lại không đúng: hai đồ thị có thể có bộ giá trị riêng giống nhau nhưng chúng không đẳng cấu. Phép nhân với ma trận hoán vị có thể được coi là việc gắn nhãn mới cho các cạnh.

Nếu A là ma trận kề của đồ thị có hướng hoặc vô hướng G, thì ma trận An (ma trận tích của n lần A) có một ý nghĩa thú vị: ô tại hàng i và cột j cho biết số đường đi (có hướng hoặc vô hướng) có độ dài n từ đỉnh i tới đỉnh j.

Ma trận I − A (trong đó I ký hiệu ma trận đơn vị n×n) là nghịch đảo được khi và chỉ khi đồ thị G không có chu trình có hướng. Khi đó, ma trận nghịch đảo (I − A)−1 có ý nghĩa sau: ô tại hàng i và cột j cho biết số đường đi có hướng từ đỉnh i tới đỉnh j (giá trị này luôn hữu hạn nếu đồ thị không có chu trình có hướng). Điều này có thể được giải thích bằng cấp số nhân (geometric series) của các ma trận:

tương ứng với thực tế rằng số đường đi từ i tới j bằng số đường đi độ dài 0 cộng với số đường đi độ dài 1 cộng với số đường đi độ dài 2 v.v...Đường chéo chính của mọi ma trận kề tương ứng của đồ thị không có khuyên gồm toàn các ô chứa giá trị 0.